package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * 好题好题, 排序都会 nlogn的排序算法也很多, 如何在链表上O1空间的排序呢?
 * -> 归并
 *
 * @author tzp
 * @since 2020/10/18
 */
public class LC148 implements LinkedProblem {
    class Pair<A, B> {
        A a;
        B b;

        Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        int step = 1;
        boolean nextStep = true;
        ListNode newHead = null;
        while (nextStep) {
            nextStep = false;
            int i = 0;
            ListNode cur = newHead == null ? head : newHead;
            ListNode pre = null, leftPre = null;
            ListNode leftStart = null, rightStart = null;
            while (cur != null) {
                if (i % step == 0) {
                    if (leftStart == null) {
                        leftPre = pre;
                        leftStart = cur;
                    } else if (rightStart == null) {
                        rightStart = cur;
                    } else if (leftStart != null && rightStart != null) {
                        nextStep = true;
                        Pair<ListNode, ListNode> merge = merge(leftStart, rightStart, step);
                        if (leftPre != null) {
                            leftPre.next = merge.a;
                        } else {
                            newHead = merge.a;
                        }
                        leftPre = merge.b;
                        leftStart = cur;
                        rightStart = null;
                    }
                }
                pre = cur;
                cur = cur.next;
                i++;
            }
            //有剩余
            if (leftStart != null && rightStart != null) {
                Pair<ListNode, ListNode> merge = merge(leftStart, rightStart, step);
                if (leftPre != null) {
                    leftPre.next = merge.a;
                } else {
                    newHead = merge.a;
                }
                leftPre = merge.b;
                leftStart = cur;
                rightStart = null;
            } else if (leftStart != null) {
                if (leftPre != null) {
                    leftPre.next = leftStart;
                } else {
                    newHead = leftStart;
                }
            }
            step = step * 2;
        }
        return newHead;
    }

    /**
     * 返回head和tail
     * 5, 4
     */
    public Pair<ListNode, ListNode> merge(ListNode leftHead, ListNode rightHead, int step) {
        int leftNum = 0, rightNum = 0;
        ListNode newHead = null;
        if (leftHead.val < rightHead.val) {
            newHead = leftHead;
            leftHead = leftHead.next;
            leftNum++;
        } else {
            newHead = rightHead;
            rightHead = rightHead.next;
            rightNum++;
        }
        ListNode newTail = newHead;
        while (leftNum < step && rightNum < step && rightHead != null) {
            if (leftHead.val < rightHead.val) {
                newTail.next = leftHead;
                newTail = newTail.next;
                leftHead = leftHead.next;
                leftNum++;
            } else {
                newTail.next = rightHead;
                newTail = newTail.next;
                rightHead = rightHead.next;
                rightNum++;
            }
        }

        if (leftNum == step) {//左用光了
            newTail.next = rightHead;
            for (int i = 0; i < step - rightNum - 1; i++) {
                if (rightHead.next == null) {
                    break;
                }
                rightHead = rightHead.next;
            }
            rightHead.next = null;
            return new Pair<>(newHead, rightHead);
        } else if (rightNum == step) {//右用光了
            newTail.next = leftHead;
            for (int i = 0; i < step - leftNum - 1; i++) {
                leftHead = leftHead.next;
            }
            leftHead.next = null;
            return new Pair<>(newHead, leftHead);
        } else {//rightHead为null了
            newTail.next = leftHead;
            for (int i = 0; i < step - leftNum - 1; i++) {
                leftHead = leftHead.next;
            }
            leftHead.next = null;
            return new Pair<>(newHead, leftHead);
        }
    }


    public static void main(String[] args) {
        ListNode listNode = ListNode.arrayToListNode(new int[]{5, 4, 3, 2, 1});
        {
//            System.out.println(new LC148().sortList(listNode));
        }
        {
            System.out.println(new LC148().sortList(ListNode.arrayToListNode(new int[]{
                    3, 2, 4
            })));
        }
//        {
//            ListNode l5 = listNode;
//            ListNode l4 = l5.next;
//            ListNode l3 = l4.next;
//            ListNode l2 = l3.next;
//            ListNode l1 = l2.next;
//
//
//            System.out.println(new LC148().merge(l5, l4, 1).a);
//            System.out.println(new LC148().merge(l3, l2, 1).a);
//
//            l5.next = l2;
//            System.out.println(l4);
//
//            System.out.println(new LC148().merge(l4, l2, 2).a);
//        }
    }
}
